package Simple5;

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;

public class threeSum {

	public static List<List<Integer>> threeSum(int[] num) {
        LinkedList<List<Integer>> ret = new LinkedList<>();
        HashSet<List<Integer>> set = new HashSet<>();
        HashMap<Integer, Integer> map = new HashMap<>();
        
        Arrays.sort(num);
        
        for(int i = 0; i < num.length; i++){
            map.put(num[i], i);
        }
            
        for(int i = 0; i < num.length; i++){
            int target = -num[i];
            for(int j = i + 1; j < num.length; j++){
            	if(num[j]==num[j-1])
            		continue;
                if(map.containsKey(target - num[j]) && map.get(target - num[j]) != j){
                    LinkedList<Integer> oneRet = new LinkedList<Integer>();
                    oneRet.add(num[i]);
                    oneRet.add(num[j]);
                    oneRet.add(target - num[j]);
                    set.add(oneRet);
                }
                
                do {
					j++;
				} while (num[j+1]==num[j]);
                
            }
                
        }
        ret.addAll(set);
        return ret;

    }
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] test =	{5,-11,-7,-2,4,9,4,4,-5,12,12,-14,-5,3,-3,-2,-6,3,3,-9,4,-13,6,2,11,12,10,-14,-15,11,0,5,8,0,10,-11,-6,-1,0,4,-4,-3,5,-2,-15,9,11,-13,-2,-8,-7,9,-6,7,-11,12,4,14,6,-4,3,-9,-14,-12,-2,3,-8,7,-13,7,-12,-9,11,0,4,12,-6,-7,14,-1,0,14,-6,1,6,-2,-9,-4,-11,12,-1,-1,10,-7,-6,-7,11,1,-15,6,-15,-12,12,12,3,1,9,12,9,0,-11,-14,-1};
		
		LinkedList<List<Integer>> ret = (LinkedList<List<Integer>>) threeSum(test);
		System.out.println(ret);
		
		
		
	}

}
